/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-05-19
 * Time: 12:37
 */
public class calculateMinimumHP {
    public int calculateMinimumHP(int[][] dungeon) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m=dungeon.length;
        int n=dungeon[0].length;
        int[][] dp=new int[m+1][n+1];
        //dp[i][j] 表⽰：从 [i, j] 位置出发，到达终点时所需的最低初始健康点数
        for (int i = 0; i <=m; i++) {
            dp[i][n]=Integer.MAX_VALUE;
        }
        for (int i = 0; i <= n; i++) {
            dp[m][i]=Integer.MAX_VALUE;
        }
        dp[m-1][n]=dp[m][n-1]=1;
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                //初始血量要大于下一个最小的初始血量
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                //如果初始血量要求小于0则换为1
                dp[i][j]=Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
}
